package single_linked_list;

public class Test {
    public static void main(String[] args) {
        SingleLinkedList list = new SingleLinkedList();
//        int[] test = new int[]{63,72,269,868,975,581,941,443,836,536,
//                824,838,282,348,109,344,196,284,502,260,327,374,932,561,199,905,668,645,151,295,7,70,582,221,
//                913,919,540,396,841,783,696,510,229,788,372,287,890,912,946,175,35,947,455,302,937,432,31,482,918,124,
//                211,526,225,459,271,125,220,958,586,498,8,50,328,949,674,354,949,259,380,834,101,218,546,274,766,311,
//                538,382,514,698,447,885,284,460,811,662,548,575,551,339,477,888,657,673,265,367,361,272,695,165,670,
//                712,235,257,85,97,723,52,620,204,952,501,204,786,718,840,388,260,63,903,537,486,940,261,894,433,670};
//        for (int i = 0; i < test.length; i++) {
//            list.addLast(test[i]);
//        }
        list.addFirst(3);
        list.addLast(3);
        list.addLast(3);
        list.addLast(4);
        list.addLast(2);
        list.addLast(5);
        list.addLast(1);
        System.out.println(list);
        list.removeIndex(6);
        System.out.println(list);
        list.removeValueOnce(3);
        System.out.println(list);
        list.removeValueAll(3);
        System.out.println(list);

//        int x = 9;
//        Node newHead = partition(list.head, 9);
//        String str = "";
//        while (newHead != null) {
//            str += newHead.value + "->";
//            newHead = newHead.next;
//        }
//        str += "NULL";
//        System.out.println(str);
//        System.out.println(chkPalindrome(list.head));
//        SingleLinkedList newList = new SingleLinkedList();
//        newList.head = list.removeAllRepeat(list.head);
//        System.out.println(newList);
//        System.out.println(list.findValue(2)); // 3
//        System.out.println(list.findIndexOnce(3)); // 2
//        list.alterValue(0, 1);
//        list.alterValue(3, 3);
//        list.alterValue(4,3);
//        System.out.println(list); // 1->1->3->3->3->NULL

//        System.out.println(Arrays.toString(list.findIndexAll(5)));
//        System.out.println(Arrays.toString(list.findIndexAll(3)));

//        list.removeIndex(0);
//        list.removeIndex(2);
//        list.removeIndex(list.size - 1);
//        System.out.println(list); // 1->3->NULL

//        list.removeValueOnce(1);
//        list.removeValueOnce(3);
//        System.out.println(list); // 1->3->3->NULL

//        list.addFirst(1); // 1->1->1->1->1->NULL
//        list.removeValueAll(1);
//        System.out.println(list); // NULL

//        list.removeValueAll(3);
//        System.out.println(list); // 1->1->3->3->3->NULL  ----->   1->1->NULL

//        list.head = SingleLinkedList.headToRemoveValueAll(list.head, 1);
//        System.out.println(list);
    }

    /**
     * 将链表分为小于X和大于x变换位置，并不更改顺序
     * @param pHead
     * @param x
     * @return
     */
    public static Node partition(Node pHead, int x) {
        // write code here
        if (pHead == null) {
            return null;
        }
        Node vHead = new Node(-1);
        vHead.next = pHead;
        Node lastNode = null;
        Node curNode = null;
        Node tempNode = vHead;
        // 找到第一个值小于x的节点作为头结点
        while(tempNode.next != null && tempNode.next.value >= x) {
            tempNode = tempNode.next;
        }
        if (tempNode.next == null) {
            return pHead;
        }
        lastNode = tempNode;
        curNode = tempNode.next.next;
        pHead = insertNode(vHead, tempNode);
        Node prevNode = pHead; // 用来记录上一个小于X的节点
        while(curNode != null) {
            if (curNode.value < x) {
                prevNode = insertNode(prevNode, lastNode);
            } else {
                lastNode = lastNode.next;
            }
            curNode = lastNode.next;
        }
        return pHead;

//        Node lessNode = null;
//        Node lessHead = null;
//        Node moreNode = null;
//        Node moreHead = null;
//        Node tempNode = pHead;
//        while (tempNode != null) {
//            if(tempNode.value < x) {
//                if(lessNode == null) {
//                    lessNode = tempNode;
//                    lessHead = lessNode;
//                }else {
//                    lessNode.next = tempNode;
//                    lessNode = lessNode.next;
//                }
//            }else{
//                if(moreNode == null) {
//                    moreNode = tempNode;
//                    moreHead = moreNode;
//                }else{
//                    moreNode.next = tempNode;
//                    moreNode = moreNode.next;
//                }
//            }
//            tempNode = tempNode.next;
//        }
//        // 注意要防止成环！！！！
//        if(moreHead != null) {
//            moreNode.next = null;
//        }
//        if (lessHead == null) {
//            return moreHead;
//        }
//        lessNode.next = moreHead;
//        return lessHead;
    }

    public static Node insertNode(Node prevNode, Node lastNode) {

        Node node = lastNode.next;
        lastNode.next = lastNode.next.next;
        node.next = prevNode.next;
        prevNode.next = node;
        return node;
    }

    /**
     * 判断是否为回文链表
     * @param head
     * @return
     */
    public static boolean chkPalindrome(Node head) {
        // 1找到中间节点
        Node fast = head;
        Node slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 2反转
        Node cur = slow.next;
        while(cur != null) {
            Node curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        // 3判断是否为回文
        while(head != slow){
            if (head.value != slow.value) {
                return false;
            }
            if (head.next == slow){
                break;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}

class SingleLinkedList {
    int size; // 指向最后一个元素的后一个位置
    Node head;

    /**
     * 判断根据index遍历、修改、删除链表结点时index的合法性
     * @param index
     * @return
     */
    private boolean isLegal(int index) {
        if (index < 0 || index >= size) {
            System.out.println("Index is illegal!");
            return false;
        }else {
            return true;
        }
    }

    /**
     * 根据头结点删除头结点对应链表中所有结点值与value相等的结点,最终返回新的头结点
     * 使用递归方法
     * 问题：这样这条单链表的size不就被破坏了吗???
     * @param headNode
     * @param value
     */
    public static Node headToRemoveValueAll(Node headNode, int value) {
        if (headNode == null) {
            return null;
        }
        // 将单链表分为size个头结点，若当前头结点的值为value则按删除头结点的方法会删除头结点即可
        headNode.next = headToRemoveValueAll(headNode.next, value);
        if (headNode.value == value) {
            Node tmpNode = headNode;
            headNode = headNode.next;
            tmpNode.next = null;
        }
        return headNode;
    }

    /**
     * 删除与value值相同的所有节点
     * @param value
     */
    public void removeValueAll(int value) {
        // 判断当前链表是否为空
        if (head == null) {
            System.out.println("SingleLinkedList is null!");
        }else {
            // 只有头结点无前驱结点，因此必须判断待删除结点是否为头结点
            while (head != null && head.value == value) {
                Node tmpNode1 = head;
                head = head.next;
                tmpNode1.next = null;
                size --;
            }
            if (head != null) {
                Node prev = head;
                while (prev.next != null) {
                    if (prev.next.value == value) {
                        Node tmpNode2 = prev.next;
                        prev.next = prev.next.next;
                        tmpNode2.next = null;
                        size --;
                    } else {
                        prev = prev.next;
                    }
                }
            }
        }
    }

    /**
     * 删除与value值相同的第一个节点
     * @param value
     */
    public void removeValueOnce(int value) {
        // 判断当前链表是否为空
        if (head == null) {
            System.out.println("SingleLinkedList is null!");
        }else {
            if (head.value == value) {
                Node tmpNode1 = head;
                head = head.next;
                tmpNode1.next = null;
                size --;
            }else {
                Node prev = head;
                while (prev.next != null) {
                    if (prev.next.value == value) {
                        Node tmpNode = prev.next;
                        prev.next = prev.next.next;
                        tmpNode.next = null;
                        size --;
                        return;
                    }
                    prev = prev.next;
                }
            }
        }
    }

    /**
     * 根据索引值删除其结点
     * @param index
     */
    public void removeIndex(int index) {
        if (isLegal(index)) {
            if (index == 0) {
                Node tmpNode1 = head;
                head = head.next;
                tmpNode1.next = null;
            }else {
                Node prev = head;
                for (int i = 1; i < index; i++) {
                    prev = prev.next;
                }
                Node tmpNode2 = prev.next;
                prev.next = prev.next.next;
                tmpNode2.next = null;
            }
            size --;
        }
    }

    /**
     * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
     * 例如，链表 1->2->3->3->4->4->5  处理后为 1->2->5
     * @param headNode
     * @return
     */
    public static Node removeAllRepeat(Node headNode) {
        if (headNode.next == null || headNode == null) {
            return headNode;
        }
        Node vHead = new Node(0);
        vHead.next = headNode;
        Node pre = vHead;
        Node cur = vHead.next;
        while (cur != null){
            if (cur.next != null && cur.value == cur.next.value) {
                cur = cur.next;
                while (cur.next != null && cur.value == cur.next.value) {
                    cur = cur.next;
                }
                cur = cur.next;
                pre.next = cur;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        return vHead.next;
    }

    /**
     * 根据索引值修改其value为newValue并返回value
     * @param index
     * @param newValue
     * @return
     */
    public int alterValue(int index, int newValue) {
        if (isLegal(index)) {
            Node cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            int tmp = cur.value;;
            cur.value = newValue;
            return tmp;
        }
        return -1;
    }

    /**
     * 找到与value值相同的所有节点的索引组成的数组
     * @param value
     * @return
     */
    public int[] findIndexAll(int value) {
        if (head == null) {
            System.out.println("SingleLinkedList is null!");
        }else {
            Node cur = head;
            String indexStr = "";
            int index = 0;
            while (cur != null) {
                if (cur.value == value) {
                    indexStr += index + " ";
                }
                index ++;
                cur = cur.next;
            }
            String[] indexChar = indexStr.split(" ");
            if (indexChar.length > 1) { // 若没有找到这个值，此时字符串为空，对应长度为一，若找到了，对应数组长度即为所有索引的个数
                int[] indexArr = new int[indexChar.length];
                for (int i = 0; i < indexChar.length; i++) {
                    indexArr[i] = Integer.parseInt(indexChar[i]);
                }
                return indexArr;
            }
        }
        return null;
    }

    /**
     * 找到与value值相同的第一个节点的索引
     * @param value
     * @return
     */
    public int findIndexOnce(int value) {
        // 判断当前链表是否为空
        if (head == null) {
            System.out.println("SingleLinkedList is null!");
        }else {
            Node cur = head;
            int index = 0;
            while (cur != null) {
                if (cur.value == value) {
                    return index;
                }
                index ++;
                cur = cur.next;
            }
        }
        return -1;
    }

    /**
     * 利用索引查找其所对应的值
     * @param index
     * @return
     */
    public int findValue(int index) {
        if (isLegal(index)) {
            Node cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            return cur.value;
        }
        return -1;
    }

    /**
     * 在链表任意位置插入
     * @param index
     * @param value
     */
    public void addIndex(int index, int value) {
        // 判断合法性
        if (index < 0 || index > size) {
            System.out.println("addIndex's index is illegal!");
            return;
        }
        if (index == 0) {
            addFirst(value);
        }else if (index == size) {
            addLast(value);
        }else {
            Node node  = new Node(value);
            // 在中间位置插入
            Node prev = head; // 寻找待插入位置的前驱结点
            for (int i = 1; i < index; i++) { // 从头结点开始到当前指定索引的前一个结点
                prev = prev.next;
            }
            node.next = prev.next;
            prev.next = node;
            size ++;
        }
    }

    /**
     * 尾插
     * @param value
     */
    public void addLast(int value) {
        Node node = new Node(value);
        // 判断链表是否为空
        if (head == null) {
            head = node;
        }else {
            Node tmpNode = head;
            while (tmpNode.next != null) {
                tmpNode = tmpNode.next;
            }
            tmpNode.next = node;
        }
        size ++;
    }

    /**
     * 头插
     * @param value
     */
    public void addFirst(int value) {
        Node node = new Node(value);
        if (head != null) { // 链表不为空
            node.next = head;
        }
        head = node;
        size ++;
    }

    public String toString() {
        Node tmpNode = head;
        String str = "";
        while (tmpNode != null) {
            str += tmpNode.value + "->";
            tmpNode = tmpNode.next;
        }
        str += "NULL";
        return str;
    }
}

class Node {
    int value;
    Node next;

    public Node() {}

    public Node(int value) {
        this.value = value;
    }
}